﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="Diff.cs" company="Joshua Tauberer's">
//  Joshua Tauberer's
// </copyright>
// <summary>
//   The diff. http://razor.occams.info/code/diff/diff/html/index.html
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace Algorithm.Diff
{
    using System;
    using System.Collections;
    using System.Text;

    /// <summary>
    /// The diff.
    /// </summary>
    public class Diff : Patch, IEnumerable
    {
        /// <summary>
        /// The _ end.
        /// </summary>
        private int _End;

        /// <summary>
        /// The _ same.
        /// </summary>
        private bool _Same;

        /// <summary>
        /// The cdif.
        /// </summary>
        private IntList cdif;

        /// <summary>
        /// The comparer.
        /// </summary>
        private readonly IComparer comparer;

        /// <summary>
        /// The hashcoder.
        /// </summary>
        private readonly IHashCodeProvider hashcoder;

        /// <summary>
        /// Initializes a new instance of the <see cref="Diff"/> class.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        public Diff(string a, string b) : this(a.ToCharArray(), b.ToCharArray(), Comparer.Default, CaseInsensitiveHashCodeProvider.Default)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Diff"/> class.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        /// <param name="casesensitive">
        /// The casesensitive.
        /// </param>
        public Diff(string[] a, string[] b, bool casesensitive) : this(a, b, casesensitive ? ((IComparer) Comparer.Default) : ((IComparer) CaseInsensitiveComparer.Default), casesensitive ? null : ((IHashCodeProvider) CaseInsensitiveHashCodeProvider.Default))
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Diff"/> class.
        /// </summary>
        /// <param name="left">
        /// The left.
        /// </param>
        /// <param name="right">
        /// The right.
        /// </param>
        /// <param name="comparer">
        /// The comparer.
        /// </param>
        /// <param name="hashcoder">
        /// The hashcoder.
        /// </param>
        public Diff(IList left, IList right, IComparer comparer, IHashCodeProvider hashcoder) : base(left, right)
        {
            this.cdif = null;
            this.comparer = comparer;
            this.hashcoder = hashcoder;
            this.init();
        }

        /// <summary>
        /// The _longest common subsequence.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        /// <param name="count">
        /// The count.
        /// </param>
        /// <returns>
        /// </returns>
        private IntList _longestCommonSubsequence(IList a, IList b, out int count)
        {
            Hashtable hashtable;
            int num = 0;
            int num2 = a.Count - 1;
            IntList list = new IntList();
            int num3 = 0;
            for (int i = 0; i < a.Count; i++)
            {
                list.Add(-1);
            }

            if (!this.IsPrepared(out hashtable))
            {
                int start = 0;
                int end = b.Count - 1;
                while (((num <= num2) && (start <= end)) && this.compare(a[num], b[start]))
                {
                    list[num++] = start++;
                    num3++;
                }

                while (((num <= num2) && (start <= end)) && this.compare(a[num2], b[end]))
                {
                    list[num2--] = end--;
                    num3++;
                }

                hashtable = this._withPositionsOfInInterval(b, start, end);
            }

            IntList array = new IntList();
            ArrayList list3 = new ArrayList();
            for (int j = num; j <= num2; j++)
            {
                IntList list4 = (IntList) hashtable[a[j]];
                if (list4 != null)
                {
                    int high = 0;
                    for (int k = 0; k < list4.Count; k++)
                    {
                        int num10 = list4[k];
                        if (((high > 0) && (array[high] > num10)) && (array[high - 1] < num10))
                        {
                            array[high] = num10;
                        }
                        else
                        {
                            high = this._replaceNextLargerWith(array, num10, high);
                        }

                        if (high != -1)
                        {
                            Trio trio = new Trio((high > 0) ? ((Trio) list3[high - 1]) : null, j, num10);
                            if (high == list3.Count)
                            {
                                list3.Add(trio);
                            }
                            else
                            {
                                list3[high] = trio;
                            }
                        }
                    }
                }
            }

            if (array.Count > 0)
            {
                count = num3 + array.Count;
                for (Trio trio2 = (Trio) list3[array.Count - 1]; trio2 != null; trio2 = trio2.a)
                {
                    list[trio2.b] = trio2.c;
                }

                return list;
            }

            count = num3;
            return list;
        }

        /// <summary>
        /// The _replace next larger with.
        /// </summary>
        /// <param name="array">
        /// The array.
        /// </param>
        /// <param name="value">
        /// The value.
        /// </param>
        /// <param name="high">
        /// The high.
        /// </param>
        /// <returns>
        /// The _replace next larger with.
        /// </returns>
        private int _replaceNextLargerWith(IntList array, int value, int high)
        {
            if (high <= 0)
            {
                high = array.Count - 1;
            }

            if ((high == -1) || (value > array[array.Count - 1]))
            {
                array.Add(value);
                return array.Count - 1;
            }

            int num = 0;
            while (num <= high)
            {
                int num2 = (high + num) / 2;
                int num3 = array[num2];
                if (value == num3)
                {
                    return -1;
                }

                if (value > num3)
                {
                    num = num2 + 1;
                }
                else
                {
                    high = num2 - 1;
                }
            }

            array[num] = value;
            return num;
        }

        /// <summary>
        /// The _with positions of in interval.
        /// </summary>
        /// <param name="aCollection">
        /// The a collection.
        /// </param>
        /// <param name="start">
        /// The start.
        /// </param>
        /// <param name="end">
        /// The end.
        /// </param>
        /// <returns>
        /// </returns>
        private Hashtable _withPositionsOfInInterval(IList aCollection, int start, int end)
        {
            Hashtable hashtable = new Hashtable(this.hashcoder, this.comparer);
            for (int i = start; i <= end; i++)
            {
                object key = aCollection[i];
                if (hashtable.ContainsKey(key))
                {
                    ((IntList) hashtable[key]).Add(i);
                }
                else
                {
                    IntList list2 = new IntList();
                    list2.Add(i);
                    hashtable[key] = list2;
                }
            }

            return hashtable;
        }

        /// <summary>
        /// The compact_diff.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        /// <returns>
        /// </returns>
        private IntList compact_diff(IList a, IList b)
        {
            IntList list;
            IntList list2;
            this.LCSidx(a, b, out list, out list2);
            IntList list3 = new IntList();
            int num = 0;
            int num2 = 0;
            list3.Add(num);
            list3.Add(num2);
            while (true)
            {
                while (((list.Count > 0) && (num == list[0])) && (num2 == list2[0]))
                {
                    list.RemoveAt(0);
                    list2.RemoveAt(0);
                    num++;
                    num2++;
                }

                list3.Add(num);
                list3.Add(num2);
                if (list.Count == 0)
                {
                    break;
                }

                num = list[0];
                num2 = list2[0];
                list3.Add(num);
                list3.Add(num2);
            }

            if ((num < a.Count) || (num2 < b.Count))
            {
                list3.Add(a.Count);
                list3.Add(b.Count);
            }

            return list3;
        }

        /// <summary>
        /// The compare.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        /// <returns>
        /// The compare.
        /// </returns>
        private bool compare(object a, object b)
        {
            if (this.comparer == null)
            {
                return a.Equals(b);
            }

            return this.comparer.Compare(a, b) == 0;
        }

        /// <summary>
        /// The create patch.
        /// </summary>
        /// <param name="direction">
        /// The direction.
        /// </param>
        /// <returns>
        /// </returns>
        public Patch CreatePatch(PatchDirection direction)
        {
            ArrayList list = new ArrayList();
            foreach (Hunk hunk in (IEnumerable) this)
            {
                if (!hunk.Same)
                {
                    if (direction == PatchDirection.LeftToRight)
                    {
                        list.AddRange(hunk.Right);
                    }
                    else
                    {
                        list.AddRange(hunk.Left);
                    }
                }
            }

            ArrayList list2 = new ArrayList();
            foreach (Hunk hunk2 in (IEnumerable) this)
            {
                if (direction == PatchDirection.LeftToRight)
                {
                    list2.Add(hunk2);
                }
                else
                {
                    list2.Add(hunk2.Reverse());
                }
            }

            return new Patch((Hunk[]) list2.ToArray(typeof(Hunk)), (object[]) list.ToArray(typeof(object)), (direction == PatchDirection.LeftToRight) ? base.Left : base.Right, (direction == PatchDirection.LeftToRight) ? base.Right : base.Left);
        }

        /// <summary>
        /// The init.
        /// </summary>
        private void init()
        {
            this.cdif = this.compact_diff(base.Left, base.Right);
            this._Same = true;
            if ((this.cdif[2] == 0) && (this.cdif[3] == 0))
            {
                this._Same = false;
                IntList list = new IntList();
                for (int i = 2; i < this.cdif.Count; i++)
                {
                    list.Add(this.cdif[i]);
                }

                this.cdif = list;
            }

            this._End = (1 + this.cdif.Count) / 2;
        }

        /// <summary>
        /// The is prepared.
        /// </summary>
        /// <param name="bMatches">
        /// The b matches.
        /// </param>
        /// <returns>
        /// The is prepared.
        /// </returns>
        private bool IsPrepared(out Hashtable bMatches)
        {
            bMatches = null;
            return false;
        }

        /// <summary>
        /// The lc sidx.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        /// <param name="b">
        /// The b.
        /// </param>
        /// <param name="am">
        /// The am.
        /// </param>
        /// <param name="bm">
        /// The bm.
        /// </param>
        private void LCSidx(IList a, IList b, out IntList am, out IntList bm)
        {
            int num;
            IntList list = this._longestCommonSubsequence(a, b, out num);
            am = new IntList();
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] != -1)
                {
                    am.Add(i);
                }
            }

            bm = new IntList();
            for (int j = 0; j < am.Count; j++)
            {
                bm.Add(list[am[j]]);
            }
        }

        /// <summary>
        /// The get enumerator.
        /// </summary>
        /// <returns>
        /// </returns>
        /// <exception cref="InvalidOperationException">
        /// </exception>
        IEnumerator IEnumerable.GetEnumerator()
        {
            if (this.cdif == null)
            {
                throw new InvalidOperationException("No comparison has been performed.");
            }

            return new Enumerator(this);
        }

        /// <summary>
        /// The to string.
        /// </summary>
        /// <returns>
        /// The to string.
        /// </returns>
        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();
            bool flag = false;
            foreach (Hunk hunk in (IEnumerable) this)
            {
                if (!hunk.Same)
                {
                    if (flag)
                    {
                        builder.Append("===================\n");
                    }

                    flag = true;
                    foreach (object obj2 in (IEnumerable) hunk.Left)
                    {
                        builder.Append("<");
                        builder.Append(obj2.ToString());
                        builder.Append("\n");
                    }

                    foreach (object obj3 in (IEnumerable) hunk.Right)
                    {
                        builder.Append(">");
                        builder.Append(obj3.ToString());
                        builder.Append("\n");
                    }

                    continue;
                }
            }

            return builder.ToString();
        }

        /// <summary>
        /// The enumerator.
        /// </summary>
        private class Enumerator : IEnumerator
        {
            /// <summary>
            /// The _ off.
            /// </summary>
            private int _Off;

            /// <summary>
            /// The _ pos.
            /// </summary>
            private int _Pos;

            /// <summary>
            /// The diff.
            /// </summary>
            private readonly Diff diff;

            /// <summary>
            /// Initializes a new instance of the <see cref="Enumerator"/> class.
            /// </summary>
            /// <param name="diff">
            /// The diff.
            /// </param>
            public Enumerator(Diff diff)
            {
                this.diff = diff;
                this.Reset();
            }

            /// <summary>
            /// The _ chk pos.
            /// </summary>
            /// <exception cref="InvalidOperationException">
            /// </exception>
            private void _ChkPos()
            {
                if (this._Pos == 0)
                {
                    throw new InvalidOperationException("Position is reset.");
                }
            }

            /// <summary>
            /// The gethunk.
            /// </summary>
            /// <returns>
            /// </returns>
            private Hunk gethunk()
            {
                this._ChkPos();
                int num5 = 1 + this._Off;
                int num6 = 2 + this._Off;
                int num = this.diff.cdif[num5 - 2];
                int num2 = this.diff.cdif[num5] - 1;
                int num3 = this.diff.cdif[num6 - 2];
                return new Hunk(this.diff.Left, this.diff.Right, num, num2, num3, this.diff.cdif[num6] - 1, this.same());
            }

            /// <summary>
            /// The move next.
            /// </summary>
            /// <returns>
            /// The move next.
            /// </returns>
            public bool MoveNext()
            {
                return this.next();
            }

            /// <summary>
            /// The next.
            /// </summary>
            /// <returns>
            /// The next.
            /// </returns>
            private bool next()
            {
                this.reset(this._Pos + 1);
                return this._Pos != -1;
            }

            /// <summary>
            /// The reset.
            /// </summary>
            /// <param name="pos">
            /// The pos.
            /// </param>
            private void reset(int pos)
            {
                if ((pos < 0) || (this.diff._End <= pos))
                {
                    pos = -1;
                }

                this._Pos = pos;
                this._Off = (2 * pos) - 1;
            }

            /// <summary>
            /// The reset.
            /// </summary>
            public void Reset()
            {
                this.reset(0);
            }

            /// <summary>
            /// The same.
            /// </summary>
            /// <returns>
            /// The same.
            /// </returns>
            private bool same()
            {
                this._ChkPos();
                if (this.diff._Same != ((1 & this._Pos) != 0))
                {
                    return false;
                }

                return true;
            }

            /// <summary>
            /// Gets Current.
            /// </summary>
            public object Current
            {
                get
                {
                    this._ChkPos();
                    return this.gethunk();
                }
            }
        }

        /// <summary>
        /// The hunk.
        /// </summary>
        public class Hunk
        {
            /// <summary>
            /// The left.
            /// </summary>
            private IList left;

            /// <summary>
            /// The right.
            /// </summary>
            private IList right;

            /// <summary>
            /// The s 1 end.
            /// </summary>
            private readonly int s1end;

            /// <summary>
            /// The s 1 start.
            /// </summary>
            private readonly int s1start;

            /// <summary>
            /// The s 2 end.
            /// </summary>
            private readonly int s2end;

            /// <summary>
            /// The s 2 start.
            /// </summary>
            private readonly int s2start;

            /// <summary>
            /// The same.
            /// </summary>
            private readonly bool same;

            /// <summary>
            /// Initializes a new instance of the <see cref="Hunk"/> class.
            /// </summary>
            /// <param name="left">
            /// The left.
            /// </param>
            /// <param name="right">
            /// The right.
            /// </param>
            /// <param name="s1start">
            /// The s 1 start.
            /// </param>
            /// <param name="s1end">
            /// The s 1 end.
            /// </param>
            /// <param name="s2start">
            /// The s 2 start.
            /// </param>
            /// <param name="s2end">
            /// The s 2 end.
            /// </param>
            /// <param name="same">
            /// The same.
            /// </param>
            internal Hunk(IList left, IList right, int s1start, int s1end, int s2start, int s2end, bool same)
            {
                this.left = left;
                this.right = right;
                this.s1start = s1start;
                this.s1end = s1end;
                this.s2start = s2start;
                this.s2end = s2end;
                this.same = same;
            }

            /// <summary>
            /// The crop.
            /// </summary>
            /// <param name="shiftstart">
            /// The shiftstart.
            /// </param>
            /// <param name="shiftend">
            /// The shiftend.
            /// </param>
            /// <returns>
            /// </returns>
            internal Hunk Crop(int shiftstart, int shiftend)
            {
                return new Hunk(this.left, this.right, this.Left.Start + shiftstart, this.Left.End - shiftend, this.Right.Start + shiftstart, this.Right.End - shiftend, this.same);
            }

            /// <summary>
            /// The diff string.
            /// </summary>
            /// <returns>
            /// The diff string.
            /// </returns>
            /// <exception cref="InvalidOperationException">
            /// </exception>
            public string DiffString()
            {
                if ((this.left == null) || (this.right == null))
                {
                    throw new InvalidOperationException("This hunk is based on a patch which does not have the compared data.");
                }

                StringBuilder builder = new StringBuilder();
                if (this.Same)
                {
                    foreach (object obj2 in (IEnumerable) this.Left)
                    {
                        builder.Append(" ");
                        builder.Append(obj2.ToString());
                        builder.Append("\n");
                    }
                }
                else
                {
                    foreach (object obj3 in (IEnumerable) this.Left)
                    {
                        builder.Append("<");
                        builder.Append(obj3.ToString());
                        builder.Append("\n");
                    }

                    foreach (object obj4 in (IEnumerable) this.Right)
                    {
                        builder.Append(">");
                        builder.Append(obj4.ToString());
                        builder.Append("\n");
                    }
                }

                return builder.ToString();
            }

            /// <summary>
            /// The equals.
            /// </summary>
            /// <param name="o">
            /// The o.
            /// </param>
            /// <returns>
            /// The equals.
            /// </returns>
            public override bool Equals(object o)
            {
                Hunk hunk = o as Algorithm.Diff.Diff.Hunk;
                return (((this.s1start == hunk.s1start) && (this.s1start == hunk.s1end)) && ((this.s1start == hunk.s2start) && (this.s1start == hunk.s2end))) && (this.same == hunk.same);
            }

            /// <summary>
            /// The get.
            /// </summary>
            /// <param name="seq">
            /// The seq.
            /// </param>
            /// <returns>
            /// </returns>
            private Range get(int seq)
            {
                int start = (seq == 1) ? this.s1start : this.s2start;
                int num2 = (seq == 1) ? this.s1end : this.s2end;
                IList list = (seq == 1) ? this.left : this.right;
                if (num2 < start)
                {
                    return new Range(list, start, 0);
                }

                return new Range(list, start, (num2 - start) + 1);
            }

            /// <summary>
            /// The get hash code.
            /// </summary>
            /// <returns>
            /// The get hash code.
            /// </returns>
            public override int GetHashCode()
            {
                return ((this.s1start + this.s1end) + this.s2start) + this.s2end;
            }

            /// <summary>
            /// The reverse.
            /// </summary>
            /// <returns>
            /// </returns>
            internal Hunk Reverse()
            {
                return new Hunk(this.right, this.left, this.Right.Start, this.Right.End, this.Left.Start, this.Left.End, this.same);
            }

            /// <summary>
            /// The set lists.
            /// </summary>
            /// <param name="left">
            /// The left.
            /// </param>
            /// <param name="right">
            /// The right.
            /// </param>
            internal void SetLists(IList left, IList right)
            {
                this.left = left;
                this.right = right;
            }

            /// <summary>
            /// The to string.
            /// </summary>
            /// <returns>
            /// The to string.
            /// </returns>
            public override string ToString()
            {
                if ((this.left == null) || (this.right == null))
                {
                    return base.ToString();
                }

                return this.DiffString();
            }

            /// <summary>
            /// Gets Left.
            /// </summary>
            public Range Left
            {
                get
                {
                    return this.get(1);
                }
            }

            /// <summary>
            /// Gets Right.
            /// </summary>
            public Range Right
            {
                get
                {
                    return this.get(2);
                }
            }

            /// <summary>
            /// Gets a value indicating whether Same.
            /// </summary>
            public bool Same
            {
                get
                {
                    return this.same;
                }
            }
        }

        /// <summary>
        /// The patch direction.
        /// </summary>
        public enum PatchDirection
        {
            /// <summary>
            /// The left to right.
            /// </summary>
            LeftToRight, 

            /// <summary>
            /// The right to left.
            /// </summary>
            RightToLeft
        }

        /// <summary>
        /// The trio.
        /// </summary>
        internal class Trio
        {
            /// <summary>
            /// The a.
            /// </summary>
            public Trio a;

            /// <summary>
            /// The b.
            /// </summary>
            public int b;

            /// <summary>
            /// The c.
            /// </summary>
            public int c;

            /// <summary>
            /// Initializes a new instance of the <see cref="Trio"/> class.
            /// </summary>
            /// <param name="a">
            /// The a.
            /// </param>
            /// <param name="b">
            /// The b.
            /// </param>
            /// <param name="c">
            /// The c.
            /// </param>
            public Trio(Trio a, int b, int c)
            {
                this.a = a;
                this.b = b;
                this.c = c;
            }
        }
    }
}

